package 二叉树;

import java.util.Arrays;

/**
 * 二叉树的修改与构造
 * User: zhaixiaolong Date:2024/3/6 9:25 ProjectName: algorithm Version:
 */
public class 二叉树的修改与构造 {


    public static void main(String[] args) {
        // 根据中序遍历和后续遍历构造二叉树
        TreeNode[] inOrder = {new TreeNode(9), new TreeNode(3), new TreeNode(15), new TreeNode(20), new TreeNode(7)};
//        TreeNode[] postOrder = {new TreeNode(9), new TreeNode(15), new TreeNode(7), new TreeNode(20), new TreeNode(3)};
//        TreeNode treeNode = buildTree(inOrder, postOrder);
        // 根据前序遍历和中序遍历构造二叉树
        TreeNode[] preOrder = {new TreeNode(3), new TreeNode(9), new TreeNode(20), new TreeNode(15), new TreeNode(7)};
        TreeNode treeNode2 = buildTree2(inOrder, preOrder);
    }

    /**
     * 根据二叉树的前序遍历和中序遍历，构造二叉树
     * 思路：取前序遍历第一个节点，此节点为根节点，用根节点切割中序遍历
     * 递归遍历
     *
     * @param inOrder   中序遍历数组
     * @param preOrder 前续遍历数组
     * @return 根节点
     */
    public static TreeNode buildTree2(TreeNode[] inOrder, TreeNode[] preOrder) {
        if (inOrder.length == 0) {
            return null;
        }
        if (inOrder.length == 1) {
            return inOrder[0];
        }
        // 根节点
        TreeNode rootNode = preOrder[0];
        // 根节点在中序遍历数组中的位置
        int inOrderRootIndex = findIndex(inOrder, rootNode);
        if (inOrderRootIndex == -1) {
            throw new RuntimeException("中序不存在节点：" + rootNode.val);
        }
        // 左右子树的中序遍历数组
        TreeNode[] leftTree = Arrays.copyOfRange(inOrder, 0, inOrderRootIndex);
        TreeNode[] rightTree = Arrays.copyOfRange(inOrder, inOrderRootIndex + 1, inOrder.length);
        // 前序遍历的最后一个元素下标
        int postRightFirstIndex = findIndex(preOrder, inOrder[inOrderRootIndex - 1]);
        // 左右子树的后序遍历数组
        TreeNode[] postLeftTree = Arrays.copyOfRange(preOrder, 1, postRightFirstIndex);
        TreeNode[] postRightTree = Arrays.copyOfRange(preOrder, postRightFirstIndex + 1, preOrder.length + 1);
        rootNode.setLeft(buildTree(leftTree, postLeftTree));
        rootNode.setRight(buildTree(rightTree, postRightTree));
        return rootNode;
    }

    /**
     * 根据二叉树的中序遍历和后序遍历，构造二叉树
     * 思路：取后序遍历最后一个节点，此节点为根节点，用根节点切割中序遍历
     * 递归遍历
     *
     * @param inOrder   中序遍历数组
     * @param postOrder 后续遍历数组
     * @return 根节点
     */
    public static TreeNode buildTree(TreeNode[] inOrder, TreeNode[] postOrder) {
        if (inOrder.length == 0) {
            return null;
        }
        if (inOrder.length == 1) {
            return inOrder[0];
        }
        // 根节点
        TreeNode rootNode = postOrder[postOrder.length - 1];
        // 根节点在中序遍历数组中的位置
        int inOrderRootIndex = findIndex(inOrder, rootNode);
        if (inOrderRootIndex == -1) {
            throw new RuntimeException("中序不存在节点：" + rootNode.val);
        }
        // 左右子树的中序遍历数组
        TreeNode[] leftTree = Arrays.copyOfRange(inOrder, 0, inOrderRootIndex);
        TreeNode[] rightTree = Arrays.copyOfRange(inOrder, inOrderRootIndex + 1, inOrder.length);
        // 后续遍历数组中，右子树第一个元素下标
        int postRightFirstIndex = findIndex(postOrder, inOrder[inOrderRootIndex + 1]);
        // 左右子树的后序遍历数组
        TreeNode[] postLeftTree = Arrays.copyOfRange(postOrder, 0, postRightFirstIndex);
        TreeNode[] postRightTree = Arrays.copyOfRange(postOrder, postRightFirstIndex, postOrder.length - 1);
        rootNode.setLeft(buildTree(leftTree, postLeftTree));
        rootNode.setRight(buildTree(rightTree, postRightTree));
        return rootNode;
    }

    /**
     * 寻找目标节点
     *
     * @param array  数组
     * @param target 目标元素
     * @return
     */
    public static int findIndex(TreeNode[] array, TreeNode target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i].val == target.val) {
                return i;
            }
        }
        return -1;
    }
}
